package main

import (
	"fmt"
	"sort"
)

func permuteUnique(nums []int) [][]int {
	sort.Ints(nums)
	return permute(nums)
}

func permute(nums []int) [][]int {
	n := len(nums)
	if n == 1 {
		return [][]int{nums}
	}
	rs := [][]int{}
	for i := 0; i < n; i++ {
		if i > 0 && nums[i] == nums[i-1] {
			continue
		}
		e := nums[i]
		copy(nums[1:], nums[:i])
		nums[0] = e
		ps := permute(nums[1:])
		for _, p := range ps {
			r := make([]int, n)
			r[0] = nums[0]
			copy(r[1:], p)
			rs = append(rs, r)
		}
		copy(nums, nums[1:i+1])
		nums[i] = e
	}
	return rs
}

func main() {
	var nums []int

	nums = []int{1, 2}
	ps := permuteUnique(nums)
	fmt.Println(ps)
	//fmt.Println(len(ps))

	nums = []int{2, 2, 2}
	fmt.Println(permuteUnique(nums))

	nums = []int{1, 1, 2}
	fmt.Println(permuteUnique(nums))

	nums = []int{1, 1, 2, 3}
	ps = permuteUnique(nums)
	fmt.Println(len(ps), ps)
}
